1. Field of the Invention
The present invention generally relates to the art of microelectronic circuit fabrication, and more specifically to a optimization processing for integrated circuit physical design automation system using optimally switched fitness improvement algorithms.
2. Description of the Related Art
1. Integrated Circuit (IC) Physical Design
2. Physical Design Algorithms
a. Overview
b. Simulated Annealing
c. Simulated Evolution
d. Force Directed Placement
3. Integrated Circuit Cell Placement Representation
4. Cost Function Computation for IC Physical Design
5. Parallel Processing Applied to IC Physical Design
6. Distributed Shared Memory (DSM) Parallel Processing Architectures
a. Overview
b. Limitations of Basic DSM Architecture
c. Telecommunications Network Applications
The automated physical design of a microelectronic integrated circuit is a specific, preferred example of simultaneous optimization processing using a parallel processing architecture to which the present invention is directed.
Microelectronic integrated circuits consist of a large number of electronic components that are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in several layers.
The layout is then checked to ensure that it meets all of the design requirements. The result is a set of design files in a particular unambiguous representation known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator.
During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design. It is an extremely tedious and an error-prone process because of the tight tolerance requirements and the minuteness of the individual components.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. However, it is expected that the feature size can be reduced to 0.1 micron within several years. This small feature size allows fabrication of as many as 4.5 million transistors or 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit, and of course, larger die (or chip) sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use Computer Aided Design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The objective of physical design is to determine an optimal arrangement of devices in a plane or in a three dimensional space, and an efficient interconnection or routing scheme between the devices to obtain the desired functionality. Since space on a wafer is very expensive real estate, algorithms must use the space very efficiently to lower costs and improve yield.
Currently available physical design automation systems are limited in that they are only capable of placing and routing approximately 20,000 devices or cells. Placement of larger numbers of cells is accomplished by partitioning the cells into blocks of 20,000 or less, and then placing and routing the blocks. This expedient is not satisfactory since the resulting placement solution is far from optimal.
An exemplary integrated circuit chip is illustrated in FIG. 1 and generally designated by the reference numeral 10. The circuit 10 includes a semiconductor substrate 12 on which are formed a number of functional circuit blocks that can have different sizes and shapes. Some are relatively large, such as a central processing unit (CPU) 14, a read-only memory (ROM) 16, a clock/timing unit 18, one or more random access memories (RAM) 20 and an input/output (I/O) interface unit 22. These blocks can be considered as modules for use in various circuit designs, and are represented as standard designs in circuit libraries.
The integrated circuit 10 further comprises a large number, which can be tens of thousands, hundreds of thousands or even millions or more of small cells 24. Each cell 24 represents a single logic element, such as a gate, or several logic elements that are interconnected in a standardized manner to perform a specific function. Cells 24 that consist of two or more interconnected gates or logic elements are also available as standard modules in circuit libraries.
The cells 24 and the other elements of the circuit 10 described above are interconnected or routed in accordance with the logical design of the circuit to provide the desired functionality. Although not visible in the drawing, the various elements of the circuit 10 are interconnected by electrically conductive lines or traces that are routed, for example, through vertical channels 26 and horizontal channels 28 that run between the cells 24.
The input to the physical design problem is a circuit diagram, and the output is the layout of the circuit. This is accomplished in several stages including partitioning, floor planning, placement, routing and compaction.
Partitioningxe2x80x94A chip may contain several million transistors. Layout of the entire circuit cannot be handled due to the limitation of memory space as well as the computation power available. Therefore it is normally partitioned by grouping the components into blocks such as subcircuits and modules. The actual partitioning process considers many factors such as the size of the blocks, number of blocks and number of interconnections between the blocks.
The output of partitioning is a set of blocks, along with the interconnections required between blocks. The set of interconnections required is referred to as a netlist. In large circuits, the partitioning process is often hierarchical, although non-hierarchical (e.g. flat) processes can be used, and at the topmost level a circuit can have between 5 to 25 blocks. However, greater numbers of blocks are possible and contemplated. Each block is then partitioned recursively into smaller blocks.
Floor planning and placementxe2x80x94This step is concerned with selecting good layout alternatives for each block of the entire chip, as well as between blocks and to the edges. Floor planning is a critical step as it sets up the ground work for a good layout. However it is computationally quite hard. Very often the task of floor plan layout is done by a design engineer using a CAD tool. This is necessary as the major components of an IC are often intended for specific locations on the chip.
Only for simple layouts can the current layout tools provide a solution without human-engineering direction and intervention. One aspect of the present invention will permit complex problems, including flow plan layout, to be accomplished without regular human intervention.
During placement, the blocks are exactly positioned on the chip. The goal of placement is to find a minimum area arrangement for the blocks that allows completion of interconnections between the blocks. Placement is typically done in two phases. In the first phase, an initial placement is created. In the second phase, the initial placement is evaluated and iterative improvements are made until the layout has minimum area and conforms to design specifications.
The vertical and horizontal channels 26 and 28 are generally provided between the blocks in order to allow for electrical interconnections. The quality of the placement will not be evident until the routing phase has been completed. A particular placement may lead to an unroutable design. For example, routing may not be possible in the space provided. In that case another iteration of placement is necessary. Sometimes routing is implemented over the entire area, and not just over the channels.
To limit the number of iterations of the placement algorithm, an estimate of the required routing space is used during the placement phase. A good routing and circuit performance heavily depend on a good placement algorithm. This is due to the fact that once the position of each block is fixed, very little can be done to improve the routing and overall circuit performance.
Routingxe2x80x94The objective of the routing phase is to complete the interconnections between blocks according to the specified netlist. First, the space not occupied by blocks, which is called the routing space, is partitioned into rectangular regions called channels and switch boxes. The goal of a router is to complete all circuit connections using the shortest possible wire length and using only the channel and switch boxes.
Routing is usually done in two phases referred to as the global routing and detailed routing phases. In global routing, connections are completed between the proper blocks of the circuit disregarding the exact geometric details of each wire and terminal. For each wire, a global router finds a list of channels that are to be used as a passageway for that wire. In other words, global routing specifies the loose route of a wire through different regions of the routing space.
Global routing is followed by detailed routing which completes point-to-point connections between terminals on the blocks. Loose routing is converted into exact routing by specifying the geometric information such as width of wires and their layer assignments. Detailed routing includes channel routing and switch box routing.
Due to the nature of the routing algorithms, complete routing of all connections cannot be guaranteed in many cases. As a result, a technique called xe2x80x9crip up and re-routexe2x80x9d is used that removes troublesome connections and re-routes them in a different order.
Compactionxe2x80x94Compaction is the task of compressing the layout in all directions such that the total area is reduced. By making the chips smaller, wire lengths are reduced which in turn reduces the signal delay between components of the circuit. At the same time a smaller area enables more chips to be produced on a wafer which in turn reduces the cost of manufacturing. Compaction must ensure that no rules regarding the design and fabrication process are violated.
VLSI physical design is iterative in nature and many steps such as global routing and channel routing are repeated several times to obtain a better layout. In addition, the quality of results obtained in one stage depends on the quality of solution obtained in earlier stages as discussed above. For example, a poor quality placement cannot be fully cured by high quality routing. As a result, earlier steps have extensive influence on the overall quality of the solution.
In this sense, partitioning, floor planning and placement problems play a more important role in determining the area and chip performance in comparison to routing and compaction. Since placement may produce an unroutable layout, the chip might need to be replaced or re-partitioned before another routing is attempted. The whole design cycle is conventionally repeated several times to accomplish the design objectives. The complexity of each step varies depending on the design constraints as well as the design style used.
The area of the physical design problem to which an aspect of the present invention relates is the placement and routing of the cells 24 and other elements on the integrated circuit 10 illustrated in FIG. 1. After the circuit partitioning phase, the area occupied by each block including the elements designated as 14 to 22 and the cells 24 can be calculated, and the number of terminals required by each block is known. In addition, the netlists specifying the connections between the blocks are also specified.
In order to complete the layout, it is necessary to arrange the blocks on the layout surface and interconnect their terminals according to the netlist. The arrangement of blocks is done in the placement phase while interconnection is completed in the routing phase. In the placement phase, the blocks are assigned a specific shape and are positioned on a layout surface in such a fashion that no two blocks are overlapping and enough space is left on the layout surface to complete interconnections between the blocks. The blocks are positioned so as to minimize the total area of the layout. In addition, the locations of the terminals on each block are also determined.
a. Overview
Very Large Scale Integrated Circuit (VLSI) physical design automation utilizes algorithms and data structures related to the physical design process. A general treatise on this art is presented in a textbook entitled xe2x80x9cAlgorithms for VLSI Physical Design Automationxe2x80x9d by Naveed Sherwani, Kluwer Academic Publishers 1993.
Depending on the input, placement algorithms can be classified into two major groups, constructive placement and iterative improvement methods. The input to the constructive placement algorithms consists of a set of blocks along with the netlist. The algorithm finds the locations of the blocks. On the other hand, iterative improvement algorithms start with an initial placement. These algorithms modify the initial placement in search of a better placement. The algorithms are applied in a recursive or an iterative manner until no further improvement is possible, or the solution is considered to be satisfactory based on a predetermined criteria.
Iterative algorithms can be divided into three general classifications, simulated annealing, simulated evolution and force directed placement. The simulated annealing algorithm simulates the annealing process that is used to temper metals. Simulated evolution simulates the biological process of evolution, while the force directed placement simulates a system of bodies attached by springs.
Assuming that a number N of cells are to be optimally arranged and routed on an integrated circuit chip, the number of different ways that the cells can be arranged on the chip, or the number of permutations, is equal to N! (N factorial). In the following description, each arrangement of cells will be referred to as a placement. In a practical integrated circuit chip, the number of cells can be hundreds of thousands or millions. Thus, the number of possible placements is extremely large.
Interactive algorithms function by generating large numbers of possible placements and comparing them in accordance with some criteria which is generally referred to as fitness. The fitness of a placement can be measured in a number of different ways, for example, overall chip size. A small size is associated with a high fitness and vice versa. Another measure of fitness is the total wire length of the integrated circuit. A high total wire length indicates low fitness and vice versa.
The relative desirability of various placement configurations can alternatively be expressed in terms of cost, which can be considered as the inverse of fitness, with high cost corresponding to low fitness and vice versa.
b. Simulated Annealing
Basic simulated annealing per se is well known in the art and has been successfully used in many phases of VLSI physical design such as circuit partitioning. Simulated annealing is used in placement as an iterative improvement algorithm. Given a placement configuration, a change to that configuration is made by moving a component or interchanging locations of two components. Such interchange can be alternatively expressed as transposition or swapping.
In the case of a simple pairwise interchange algorithm, it is possible that a configuration achieved has a cost higher than that of the optimum, but no interchange can cause further cost reduction. In such a situation, the algorithm is trapped at a local optimum and cannot proceed further. This happens quite often when the algorithm is used in practical applications. Simulated annealing helps to avoid getting stuck at a local optima by occasionally accepting moves that result in a cost increase.
In simulated annealing, all moves that result in a decrease in cost are accepted. Moves that result in an increase in cost are accepted with a probability that decreases over the iterations. The analogy to the actual annealing process is heightened with the use of a parameter called temperature T. This parameter controls the probability of accepting moves that result in increased cost.
More of such moves are accepted at higher values of temperature than at lower values. The algorithm starts with a very high value of temperature that gradually decreases so that moves that increase cost have a progressively lower probability of being accepted. Finally, the temperature reduces to a very low value which requires that only moves that reduce costs are to be accepted. In this way, the algorithm converges to an optimal or near optimal configuration.
In each stage, the placement is shuffled randomly to get a new placement. This random shuffling could be achieved by transposing a cell to a random location, a transposition of two cells, or any other move that can change the wire length or other cost criteria. After the shuffle, the change in cost is evaluated. If there is a decrease in cost, the configuration is accepted. Otherwise, the new configuration is accepted with a probability that depends on the temperature.
The temperature is then lowered using some function which, for example, could be exponential in nature. The process is stopped when the temperature is dropped to a certain level. A number of variations and improvements on the basic simulated annealing algorithm have been developed. An example is described in an article entitled xe2x80x9cTimberwolf 3.2 A New Standard Cell Placement and Global Routing Packagexe2x80x9d by Carl Sechen, et al., IEEE 23rd Designed Automation Conference paper 26.1, pages 432 to 439.
c. Simulated Evolution
Simulated evolution, which is also known as the genetic algorithm, is analogous to the natural process of mutation of species as they evolve to better adapt to their environment. The algorithm starts with an initial set of placement configurations which is called the population. The initial placement can be generated randomly. The individuals in the population represent a feasible placement to the optimization problem and are actually represented by a string of symbols.
The symbols used in the solution string are called genes. A solution string made up of genes is called a chromosome. A schema is a set of genes that make up a partial solution. The simulated evolution or genetic algorithm is iterated, and each iteration is called a generation. During each iteration, the individual placements of the population are evaluated on the basis of fitness or cost. Two individual placements among the population are selected as parents, with probabilities based on their fitness. The better fitness a placement has, the higher the probability that it will be chosen.
The genetic operators called crossover, mutation and inversion, which are analogous to their counterparts in the evolution process, are applied to the parents to combine genes from each parent to generate a new individual called the offspring or child. The offspring are evaluated, and a new generation is formed by including some of the parents and the offspring on the basis of their fitness in a manner such that the size of the population remains the same. As the tendency is to select high fitness individuals to generate offspring, and the weak individuals are deleted, the next generation tends to have individuals that have good fitness.
The fitness of the entire population improves over the generations. That means that the overall placement quality improves over iterations. At the same time, some low fitness individuals are reproduced from previous generations to maintain diversity even though the probability of doing so is quite low. In this way, it is assured that the algorithm does not get stuck at some local optimum.
The first main operator of the genetic algorithm is crossover, which generates offspring by combining schemata of two individuals at a time. This can be achieved by choosing a random cut point and generating the offspring by combining the left segment of one parent with the right segment of the other. However, after doing so, some cells may be duplicated while other cells are deleted. This problem will be described in detail below.
The amount of crossover is controlled by the crossover rate, which is defined as the ratio of the number of offspring produced by crossing in each generation to the population size. Crossover attempts to create offspring with fitness higher than either parent by combining the best genes from each.
Mutation creates incremental random changes. The most commonly used mutation is pairwise interchange or transposition. This is the process by which new genes that did not exist in the original generation, or have been lost, can be generated.
The mutation rate is defined as the ratio of the number of offspring produced by mutation in each generation to the population size. It must be carefully chosen because while it can introduce more useful genes, most mutations are harmful and reduce fitness. The primary application of mutation is to pull the algorithm out of local optima.
Inversion is an operator that changes the representation of a placement without actually changing the placement itself so that an offspring is more likely to inherit certain schema from one parent.
After the offspring are generated, individual placements for the next generation are chosen based on some criteria. Numerous selection criteria are available, such as total chip size and wire length as described above. In competitive selection, all the parents and offspring compete with each other, and the fittest placements are selected so that the population remains constant. In random selection, the placements for the next generation are randomly selected so that the population remains constant.
The latter criteria is often advantageous considering the fact that by selecting the fittest individuals, the population converges to individuals that share the same genes and the search may not converge to an optimum. However, if the individuals are chosen randomly there is no way to gain improvement from older generation to new generation. By combining both methods, stochastic selection makes selections with probabilities based on the fitness of each individual.
d. Force Directed Placement
Force directed placement exploits the similarity between the placement problem and the classical mechanics problem of a system of bodies attached to springs. In this method, the blocks connected to each other by nets are supposed to exert attractive forces on each other. The magnitude of this force is directly proportional to the distance between the blocks. Additional proportionality is achieved by connecting more xe2x80x9cspringsxe2x80x9d between blocks that xe2x80x9ctalkxe2x80x9d to each other more (volume, frequency, etc.) and fewer xe2x80x9cspringsxe2x80x9d where less extensive communication occurs between each block.
According to Hooke""s Law, the force exerted due to the stretching of the springs is proportional to the distance between the bodies connected to the spring. If the bodies are allowed to move freely, they would move in the direction of the force until the system achieved equilibrium. The same idea is used for placing the cells. The final configuration of the placement of cells is the one in which the system achieves a solution that is closest to or in actual equilibrium.
Using physical design algorithms as discussed above, each cell placement is conventionally represented in the form of a list or table including locations on the chip and identifiers of the cells that are assigned to the respective locations. As indicated at 30 in FIG. 2, an exemplary and greatly simplified cell placement includes nine cell locations that are designated as (1) to (9), and cells that are indicated by identifiers 1 to 9. The locations are numbered in consecutive order from left to right and top to bottom.
The cell locations are designated by numbers in parenthesis, whereas the cell identifiers are designated only as numbers. Although only nine cell locations are illustrated as constituting the placement 30, it will be understood that an actual integrated circuit chip can include hundreds of thousands, millions or more of cell locations.
The cells in the placement 30 can be represented by a table or list as indicated at 32. The list 32 is comparable to a chromosome in biological genetics, whereas each entry in the list 32 is analogous to a gene. In a more general sense, the entries in the list can be considered as abstract entities, whereas the list can be considered as a permutation of the entities.
In genetic mutation, a new placement is produced from an initial placement by transposing individual cells. Genetic inversion involves reversing the order of a group of consecutive cells. These operations can be performed using the conventional placement representation illustrated in FIG. 2 without problems. However, attempting to perform genetic crossover using the conventional representation will result in duplication and/or omission of cells, and other illegal placements.
The reason that the conventional placement representation is not applicable to straight genetic crossover is illustrated in FIG. 2. In the illustrated example, a second placement 34 is provided as represented by a list 36. The placements 30 and 34, which are referred to as xe2x80x9cparentsxe2x80x9d, are genetically crossed with each other to produce two new placements 38 and 40 that are represented by lists 42 and 44 respectively. The new placements 38 and 40 are referred to as xe2x80x9coffspringxe2x80x9d or xe2x80x9cchildrenxe2x80x9d.
The placement 30 consists of cells 1 to 9 in locations (1) to (9) respectively. The placement 34 consists of cells 4 to 9 and 1 to 3 in locations (1) to (9) respectively. It will be understood that the particular numerical arrangement of cells in the placements 30 and 34 is arbitrary, and that the principles involved could be alternatively illustrated and described using any numerical arrangement.
In FIG. 2, genetic crossover is performed by transposing or xe2x80x9cswappingxe2x80x9d the last four elements in the lists 32 and 36. This produces the placement 38 as represented by the list 42 which includes the first five elements in the list 32 and the last four elements in the list 36. The crossover further produces the placement 40 as represented by the list 44 which includes the first five elements in the list 36 and the last four elements in the list 32.
Both of the exemplary placements are illegal, in that they include duplications and omissions of cells. In the placement 38, the cells 1, 2 and 3 are each represented twice, whereas the cells 6, 7 and 8 are omitted. In the placement 40, the cells 6, 7 and 8 are each represented twice, whereas the cells 1, 2 and 3 are omitted. It is clear that this method is inapplicable to the physical design of integrated circuit chips because the circuits would be inoperative if cells were duplicated and/or omitted.
An expedient for bypassing this problem is described in an article entitled xe2x80x9cA GENETIC APPROACH TO STANDARD CELL PLACEMENT USING META-GENETIC PARAMETER OPTIMIZATIONxe2x80x9d, by Khushro Shahookar et al, in IEEE Transactions on Computer-Aided Design, Vol. 9, No. 5, May 1990, pp. 500-511. Shahookar accomplishes his goal by utilizing a complicated modification of genetic crossover referred to in the article as xe2x80x9ccycle crossoverxe2x80x9d. Other modified crossover operations which are discussed by Shahookar are referred to as xe2x80x9corder crossoverxe2x80x9d and xe2x80x9cpartially mapped crossoverxe2x80x9d (PMX).
The design of an integrated circuit chip requires the placement and routing of at least thousands of cells. The additional computing time required for the implementation of Shahookar""s methods increases the total computer time for a typical integrated circuit design to such an inordinate value that it would be impractical to implement in a commercial production environment.
FIGS. 3 and 4 illustrate a xe2x80x9chalf-perimeterxe2x80x9d wire length computation method which is known in a basic form in the art per se. This method is described in the above referenced article to Sechen, and is advantageous in that it can be performed quickly in a non-computationally intensive manner.
In FIG. 3, a cell placement 46 includes a plurality of cells 48 that are allocated to respective locations on a surface 50 representing an integrated circuit chip. A netlist for the placement includes a list of nets, each of which interconnects terminals on cells that are to be electrically equivalent. An exemplary net 52 is illustrated in the drawing as interconnecting terminals 54, 56 and 58 of cells 48a, 48b and 48c respectively.
The wirelength of the net 52 is estimated by defining or constructing a rectangular xe2x80x9cbounding boxxe2x80x9d 60 that surrounds the outermost terminals of the net 52 and is spaced outwardly therefrom in the horizontal and vertical directions by a xe2x80x9cdetour factorxe2x80x9d xcex4 that allows for variations in the actual interconnect routing. The wirelength of the net 52 is computed or approximated as the half-perimeter, or the sum of the width and height of the bounding box 60.
In the example of FIG. 3, the net 52 includes a horizontal leg between the terminals 54 and 56 that is approximately equal to the width of the bounding box 60, and a vertical leg between the terminals 56 and 58 that is approximately equal to the height of the bounding box 60. Thus, the half-perimeter method provides a good approximation of the wirelength of the net 52.
However, this is not always the case. For example, as illustrated in FIG. 4, a placement 64 includes a plurality of cells 66 on a surface 68. A net 70 interconnects terminals 72, 74, 76, 78, 80, 82, and 84 of cells 66a, 66b, 66c, 66d, 66e and 66f. The net 70 is enclosed by a bounding box 86.
The net 70 includes a lower horizontal leg and a vertical leg that extends between the terminals 72 and 84. The lengths of these legs in combination is approximately equal to the half-perimeter of the bounding box 86. However, the net 70 further includes a plurality of vertical legs extending from the lower horizontal leg to the terminals 74, 76, 78, 80, 82 and 84.
The lengths of these vertical legs, in combination with the lengths of the legs extending between the terminals 72 and 84, substantially exceed the half-perimeter of the bounding box 86. In this case, the half-perimeter estimation would produce a computed value of wirelength for the net 70 that is unrealistically low, and indicates a lower value of congestion than would actually be present.
A major factor that prevents conventional algorithms from being utilized for the placement and routing of larger number of cells is that the physical design problem is executed using serial or uniprocessor computers. Numerous iterations of the placement and general and detailed routing algorithms are necessary before the solution converges to an optimal design. Execution of these iterations is extremely time consuming, requiring days, or even weeks or months to produce a design for a large integrated circuit.
In addition, human intervention is required for all but the simplest designs. Since each stage of iteration inherits the results, but not the details, of the previous operational stage, no sharing of information between stages, such as placement and global routing, that could result in faster convergence, is inherent in the process. Feedback of routing information, for example, could speed up convergence of the placement operation. Since this does not occur, a large number of non-optimal solutions are generated, and a human technician is required to obtain an overview of the process and divert it away from false and/or inefficient solutions.
An implementation in which the genetic algorithm is executed in parallel on separate computers is described in an article entitled xe2x80x9cWOLVERINES: STANDARD CELL PLACEMENT ON A NETWORK OF WORKSTATIONSxe2x80x9d, by S. Mohan et al, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 12, No. 9, September 1993, pp. 1312-1326. The procedure runs a basic genetic algorithm on each of a plurality of computer-aided-design (CAD) workstation in the network and utilizes an additional genetic operator, migration, which transfers placement information from one workstation to another across the network. Migration transfers genetic material from one environment to another, thereby introducing new genetic information and modifying the new environment.
If the migrants are fitter than the existing individuals in the new environment, they get a high probability of reproduction and their genetic material is incorporated into the local population. When the population is very small it tends to converge after a few generations, in the sense that all the individuals come to resemble one another. Migration prevents this premature convergence of inbreeding by introducing new genetic material. In this manner, the genetic algorithm is modified by splitting the large population over different workstations and using the migration mechanism to prevent premature convergence.
Although Mohan discloses the general concept of parallel processing of genetic algorithms, he teaches a procedure in which the various stages of integrated circuit chip design are performed in series, with no feedback or sharing of information between stages until an entire design is completed or at least the global routing stage is completed.
a. Overview
An architecture including a plurality, preferably many parallel processors that is especially suited for application to physical design automation of integrated circuits is known as cache coherent Distributed Shared Memory (DSM). Two examples of this architecture are presented in an article entitled xe2x80x9cThe Stanford Dash Multiprocessorxe2x80x9d, by Daniel Lenoski et al, et al, in Computer Magazine, March 1992, pp. 63-79, and in a technical summary of the KSR1 System prepared by Kendall Square Research, of Waltham, Mass., 1992.
A basic DSM architecture of the type described in the article to Lenoski (the DASH system) is illustrated in FIG. 5. A DSM system 90 includes processors 92, 94, and 96, 98 that are arranged in two clusters 100 and 102 respectively. Cache memories 104, 106, 108 and 110 are connected to the processors 92, 94, 96 and 98 respectively. The cluster 100 further includes a shared memory 112 and a directory 114, whereas the cluster 102 further includes a shared memory 116 and a directory 118. The clusters 100 and 102 communicate with each other via an interconnection network 120.
Although only four processors are illustrated in FIG. 38, in a practical application the number of processors will preferably be tens, hundreds or even thousands. The caches 104 and 106, shared memory 112 and directory 114 are interconnected by a snooping bus 122, whereas the caches 108 and 110, shared memory 116 and directory 118 are interconnected by a snooping bus 124.
The arrangement of FIG. 5 is advantageous in that all of the memory in the system, consisting of the caches 104, 106, 108 and 110 and shared memory 112 and 116, is available for use by all of the processors 92, 94, 96 and 98, and the memory is scalable. The memory used by each processor can be dynamically allocated depending on the requirements of a particular task.
However, the memory access times are different depending on the type of access. The processors can access the caches that are directly connected thereto at a highest speed, and access the shared memory in their respective cluster at a lower speed. A processor in one cluster can access a cache or shared memory in another cluster via the interconnection network 120, but at a yet lower speed.
The snooping buses 122 and 124 provide cache coherence within the clusters 100 and 102 respectively, whereas the directories 114 and 118 provide cache coherence for the entire system 90. In the cache coherence scheme, multiple copies of a particular data block can exist in the different memories of the system. The directories 114 and 118 keep track of which data blocks are stored in which memories.
If a data block is altered by any of the processors, the unmodified copies in other memories are either invalidated or updated. If invalidation is used, the relevant directory 114 or 118 sends messages only to the memories that contain the unmodified copies to indicate that the copies are no longer valid. Where updating is used, copies of the modified block are sent to the memories in which the original copies were stored.
b. Limitations of Basic DSM Architecture
In applying genetic algorithms and other fitness improvement operations to solving integrated circuit cell placement and other optimization problems, an important issue is that the computational requirements increase very rapidly with problem size. The size of the xe2x80x9cDNAxe2x80x9d or data structure representing a member of the population or placement increases with the problem size. The size of the population required to find the optimum placement also increases with the problem size, so the memory requirements increase very rapidly.
The time required to perform a fitness calculation increases with the size of the DNA, and the number of fitness calculations required per generation increases with the size of the population. The number of generations required to reach a solution increases with the size of the population.
Thus, the computation time increases rapidly with problem size. Taking the memory requirements and computation time together, the computational requirements increase very rapidly with problem size. For example, using a genetic algorithm to find an optimal placement of 9 cells takes a few seconds, 25 cells takes a few minutes, and 100 cells takes a few hours, using an industry Standard Performance Evaluation Criteria (SPEC) 50 workstation. Using this approach to find an optimal placement of a state-of-the-art chip with 100,000 or more cells is not feasible.
In a DSM system such as described above with reference to FIG. 5, a shared or main memory is provided for data that is more global, operated on by more than one processor, or is too large to be stored in a local cache memory. A scalable mechanism, typically a directory structure, is provided to maintain the main memory and all of the cache memories coherent with each other.
The directory logic enables any processor to access data in the main memory or in any cache memory, and invalidates or updates any obsolete copies of data. The directory based DSM architecture is especially advantageous in that the memory bandwidth scales with the number of processors.
In view of the numerous advantages provided by the DSM architecture, it would be desirable to integrate a DSM node on a single integrated circuit chip. However, the inherent characteristics of the conventional DSM design frustrate the accomplishment of this goal using presently available microelectronic circuit fabrication technology.
More specifically, it is highly preferable to store data in a local cache memory, which is generally implemented as Static Random Access Memory (SRAM) rather than in a main memory, which is generally implemented as Dynamic Random Access Memory (DRAM) due to the much lower latency and access time. However, if a cache memory is not large enough, some of the data that is required to be stored must be directed to the main memory. This data is said to xe2x80x9cmissxe2x80x9d the cache memory, and the number of memory access operations that must be performed using the main memory is referred to as the xe2x80x9ccache miss ratexe2x80x9d.
Since the latency of the main memory is much higher than that of the cache memory, a large cache memory is required to provide an acceptably low cache miss rate. The time required to process a cache miss, which is referred to as the xe2x80x9ccache miss resolution periodxe2x80x9d or xe2x80x9ccache miss costxe2x80x9d, includes the time required to access the main memory in addition to performing requisite housekeeping functions.
The processor that ordered the memory access operation which resulted in the cache miss is xe2x80x9cstalledxe2x80x9d during the cache resolution period, and cannot execute any other instructions until the memory access operation is completed.
Assuming a 100 Mhz clock rate, a cache memory access operation can be typically performed in 10 ns, whereas a typical cache miss resolution period or cost is on the order of 200 to 500 ns. If the cache miss rate is high and the instructions being processed are memory intensive, the processing speed can be reduced to such an extent that the system can operate at an effective clock rate of as low as 2 MHz.
For this reason, the cache memory in a conventional DSM system is made sufficiently large to reduce the cache miss rate to a level at which the processing speed is not unacceptably degraded. However, a cache memory of conventional size is too large to fit on a single integrated circuit chip together with a processor, main memory and the requisite logic and control circuitry.
The problem is exacerbated by the fact that cache memory is conventionally implemented as SRAM, whereas main memory is implemented as DRAM. SRAM has a much lower gate or cell density than DRAM. For example, assuming a CMOS process with a feature size of 0.5 xcexcm, the SRAM density is typically 2 kilobytes per square millimeter, whereas the DRAM density is 32 kilobytes per square millimeter.
The high latency and cache miss cost for main memory access in a conventional multi-chip DSM system, even if a large cache memory is provided to reduce the cache miss rate, reduce the effective processing speed to such an extent that complicated processors are required to increase the processing speed to an acceptable value.
An example of such a processor is a xe2x80x9csuperscalarxe2x80x9d processor that executes several instructions simultaneously using an asynchronous pipelining system. In addition to being complicated and expensive, such processors are too large to fit on a single integrated circuit chip together with the other elements of a DSM node.
c. Telecommunications Network Applications
Electronic data networks are becoming increasingly widespread for the communication of divergent types of data including computer coded text and graphics, voice and video. Such networks enable the interconnection of large numbers of computer workstations, telephone and television systems, video teleconferencing systems and other facilities over common data links or carriers.
Computer workstations are typically interconnected by local area networks (LAN) such as Ethernet, Token Ring, DECNet and RS-232, whereas metropolitan, national and international systems are interconnected by wide area networks (WAN) such as Ti, V3.5 and FDDI.
Although effective, communication using these networks is relatively slow, and a complicated and expensive network interface adapter must be provided for each device that is to be connected to a network.
1. Generalized Optimization Processing Using Decomposition and Simultaneous Processing
2. Optimization Processing for Integrated Circuit (IC) Physical Design Automation
3. Hierarchial Execution by Asynchronous Delegation (HEADWARE)
4. Integrated Circuit Cell Placement Representation
5. Congestion Based Cost Function Computation
6. Improved Genetic Algorithms for Physical Design Automation
7. Optimal Switching of Algorithms
8. Optimal Switching of Cost Functions
9. Simultaneous Placement and Routing (SPAR)
10. Moving Windows
11. Chaotic Placement
12. Single Chip Distributed Shared Memory Node
13. Single Chip Communications Node
The present invention provides a method of process decomposition and optimization utilizing massively parallel simultaneous processors that is especially suited to integrated circuit cell placement optimization.
The present method is not limited to any specific application, however, and can be advantageously applied to optimization problems in a number of diverse areas such as logic synthesis, circuit optimization (for minimum power, etc.), software optimization, logistical problems such as traffic control and routing.
In general, the present method can be utilized to obtain solutions to optimization problems having many simple or complex variables that are interrelated. For example, further applications of the invention include financial market and investment analysis, currency arbitrage, weather forecasting, seismic and nuclear analysis and maintenance of complex databases.
In each application of the present method for producing an optimized solution to a problem, a methodology for solving the problem and/or data representing the problem are decomposed into a plurality of tasks that are performed simultaneously to produce a result for each task. The results are then recomposed to produce an optimized solution to the problem.
The optimized solution is analyzed to produce an evaluation, and the steps of performing the tasks, recomposing the results and analyzing the optimized solution to produce an evaluation are repeated to further optimize the optimized solution if the evaluation does not satisfy a predetermined criterion.
In a physical design automation system for producing an optimized cell placement for an integrated circuit chip, a placement optimization methodology is decomposed into a plurality of cell placement optimization processes that are performed simultaneously by parallel processors on input data representing the chip.
The results of the optimization processes are recomposed to produce an optimized cell placement. The fitness of the optimized cell placement is analyzed, and the parallel processors are controlled to selectively repeat performing the optimization processes for further optimizing the optimized cell placement if the fitness does not satisfy a predetermined criterion.
The system can be applied to initial placement, routing, placement improvement and other problems.
The processors can perform the same optimization process on different placements, or on areas of a single placement. Alternatively, the processors can perform different optimization processes simultaneously on a single initial placement, with the resulting processed placement having the highest fitness being selected as the optimized placement.
The processors can further selectively reprocess areas of a placement having high cell interconnect congestion or other low fitness parameters.
In accordance with a massively parallel simultaneous processing methodology of the present invention, a master or host process, which can be referred to as a team leader in the present xe2x80x9cHEADWARExe2x80x9d concept, is first started. The team leader assigns tasks to worker processes and collects results. The present method uses very little computer time and can service a large number of worker processes.
When a worker process is started, the first thing it does is to send a message to the team leader requesting a task. The team leader then replies with a message assigning a task and marks the task as having been assigned. Communication between the team leader and the worker then ceases, leaving the team leader free to communicate with other workers.
It is not necessary for the team leader to record which worker was assigned a particular task, or when the task was assigned. An arbitrary number of workers can request tasks in this manner, with the team leader assigning each worker a previously unassigned task.
When a worker completes a task, it resumes communication with the team leader and identifies the task that it was assigned, and the results that were obtained from performing the task. The team leader then records the results, marks the task as having been completed and assigns the worker another task. The team leader further preferably saves a copy of the task list on a computer disk or the like at periodic intervals as a precaution against failure of the team leader process.
A large number of possible cell placements for an integrated circuit chip are evaluated to determine which has the highest fitness in accordance with a predetermined criteria such as interconnect congestion. Each cell placement, which constitutes an individual permutation of cells from a population of possible permutations, is represented as an initial cell placement in combination with a list of individual cell transpositions or swaps by which the cell placement can be derived from the initial cell placement.
A cell placement can be genetically mutated and/or inverted by adding swaps to the list for its cell placement which designates cells to be transposed. Genetic crossover can be performed by transposing swaps between the lists for two cell placements.
The present cell representation and transposition method enables any type of cell transposition to be performed without loss or duplication of cells or generation of illegal placements.
The fitness of each integrated circuit cell placement is evaluated by dividing the placement into rectangular areas we call switch boxes that surround the cell locations respectively. A bounding box is constructed around each net of a netlist for the placement. A congestion factor is computed for each switch box, for example, as being equal to the number of bounding boxes that overlap the respective switch box.
A cost factor for the placement and associated netlist, which is an inverse measure of the fitness, is computed as the maximum value, average value, sum of squares or other function of the congestion factors.
The individual congestion factor computations can be modified to require that a terminal of a net of one of the bounding boxes overlap or be within a predetermined distance of a switch box in order for the congestion factor to be computed as the sum of the overlapping bounding boxes in order to localize and increase the accuracy of the cost factor estimation. The congestion factor for a switch box can also be weighted in accordance with the proximity of the switch box to a terminal.
Cells for transposition or xe2x80x9cswappingxe2x80x9d within each placement using genetic algorithms are selected using, for example, greedy algorithms based on the fitness of each cell. The cell fitnesses are evaluated in terms of interconnect congestion, total net wire length or other criteria.
Cells are selected for genetic crossover by sorting the cells in order of fitness and multiplying the cell fitnesses by weighting factors that increase non-linearly with rank. The cells are selected using linear or random or pseudo-random or patterned number generation such that cells with higher fitnesses have a higher probability of selection.
Cells having lowest fitness are selected for mutation, and transposed to random locations, to adjacent locations, with cells having second worst fitness, to the center of mass of the respective interconnect nets, or with two or more cells in a cyclical manner.
Two or more fitness improvement algorithms are available, and are optimally switched from one to the other in accordance with an optimization criterion to maximize convergence of the placements toward the optimal configuration.
Two or more fitness (cost) calculation functions are available, and are optimally switched from one to the other in accordance with a optimization criterion.
A method for optimizing a cell placement for an integrated circuit chip includes decomposing an initial placement of cells into a hierarchial order of groups of cells. The groups are routed simultaneously using parallel processors, and the results are recomposed to provide a global routing that provides a detailed mapping of cell interconnect congestion in the placement.
Areas of high congestion are identified, and a congestion reduction algorithm is applied using the parallel processors to alter the placement in these areas simultaneously. The overall fitness of the placement is then computed, and if it has not attained a predetermined value, the steps of identifying congested areas and applying the congestion reduction algorithm to these areas are repeated.
The present invention advantageously utilizes detailed congestion information provided by the global routing. However, global routing is very time consuming, and impractical to perform after each local congestion reduction iteration within the limits of current microelectronic circuit technology.
The present invention avoids this problem by estimating the cumulative error created by altering the placement without repeating global routing, and repeating the global routing only if the error exceeds a predetermined value. This enables a number of improvement operations to be performed and their results evaluated before another global routing is required, thereby greatly speeding up the optimization process.
The present methodology, in combination with simultaneous parallel processing applied to routing and fitness improvement and immediate feedback of improvement results to the congestion reduction processing, reduces the time required for placement optimization to a level that can be advantageously realized in a practical implementation.
One or more non-overlapping moving windows are positioned over a placement of cells for an integrated circuit chip to delineate respective subsets of cells. A fitness improvement operation such as simulated evolution is performed on the subsets simultaneously using parallel processors.
The windows may be either moved to specifically identified high interconnect congestion areas of the placement, or are moved across the placement in a raster type or other organized or random pattern such that each area of the placement is processed at least once. Exchange of misplaced cells between subsets can be accomplished by dimensioning the windows and designing the window movement pattern such that the subsets overlap. Alternatively, such exchange can be accomplished by using two sets of windows of different sizes.
As yet another alternative, the improvement operation can allow misplaced cells to be moved to a border area outside a window. Each misplaced cell is placed on a list, and then moved to the centroid of the group of cells to which it is connected, which can be outside the subset that originally included the misplaced cell.
Dividing the chip into xe2x80x9cmoving windowsxe2x80x9d and optimizing the placement within each window reduces the time required to find a solution. It has two major advantages. By applying a genetic algorithm or other fitness improvement operation only to cells within the window, the size of the problem is much smaller, and the computational requirements are dramatically reduced. Also, each window can be assigned to a different processor of a suitable multiprocessor computer, so the optimization of the windows can be done simultaneously in parallel, reducing the wall-clock time required to find the solution.
In a xe2x80x9cchaoticxe2x80x9d placement method of the present invention, the fitness of a cell placement for an integrated circuit chip is optimized by relocating at least some of the cells to new locations that provide lower interconnect congestion. For each cell, the centroid of the group of cells to which the cell is connected is computed. The cell is then moved toward the centroid by a distance that is equal to the distance from the current position of the cell to the centroid multiplied by a xe2x80x9cchaosxe2x80x9d factor xcex.
The value of xcex is selected such that the cell relocation operations will cause the placement to converge toward an optimal configuration without chaotic diversion, but with a sufficiently high chaotic element to prevent the optimization operation from becoming stuck at local fitness optima.
The new cell locations can be modified to include the effects of cells in other locations, such as by incorporating a function of cell density gradient or force direction into the computation. This spreads out clumps of cells so that the density of cells is more uniform throughout the placement. The attraction between cells in the nets is balanced against repulsion caused by a high local cell density, providing an optimized tradeoff of wirelength, feasibility and congestion.
The present invention overcomes the problems discussed above regarding conventional multi-chip Distributed Shared Memory (DSM) systems, and provides a complete DSM node that is integrated on a single integrated circuit chip.
In accordance with the invention, the capacity of a cache memory is substantially reduced over that required for a multi-chip DSM implementation to enable the cache memory, a main memory, a processor and requisite logic and control circuitry to fit on a single integrated circuit chip.
The increased cache miss rate created by the reduced cache memory capacity is compensated for by the reduced cache miss resolution period or cost resulting from integrating the main memory and processor on the single chip. The reduced cache miss resolution period enables the processor clock rate to be substantially increased, so that a processor having a simple functionality such as a reduced instruction set computer (RISC) processor can be utilized and still provide the required processing speed.
The RISC processor is substantially smaller than a more complicated processor that would be required to provide the same processing speed in a multi-chip DSM implementation, thereby enabling the RISC processor to fit on the chip with the other elements.
The smaller and less expensive RISC processor increases the number of processors that can be connected to a main memory of predetermined size. This increases the number of processors that can simultaneously operate on a problem defined by the main memory space and thereby increases the computational efficiency, and also reduces the amount of main memory that is required for each processor. This further enhances the ability of the present DSM node to be implemented on a single integrated circuit chip.
The present invention provides a single-chip communications node that can be used in telecommunications networks other than DSM, and is faster in operation, simpler in construction and less expensive to manufacture and implement than conventional network interfaces.
The present communications node includes a memory controller for providing local and remote memory coherency, and a bidirectional interconnect unit that converts memory access instructions into memory access messages and vice-versa.
The above and other objects, features and advantages of the present invention will become apparent to those skilled in the art from the following detailed description taken with the accompanying drawings, in which like reference numerals refer to like parts.